(づ｡◕‿◕｡)づ
嗨，我是wec，今天是DAY 6。

🔎 題目難度與描述

難度：EASY

題目描述：

給定一個整數數組prices，其中prices[i]代表某支股票在第i天的價格。
只能選擇某一天買入這支股票，並選擇在之後的一天賣出，並找出能夠獲得的最大利潤（不能在買入股票前賣出股票）如果無法獲得任何利潤，返回0。

🔎 解題思路＆程式碼

1️⃣ 貪婪演算法 Greedy Algorithm

第1步： 假設我們還沒有遇到任何低價，所以我們用一個「超巨的數字」當作最低價格的初始值（因為不可能有股價會超過這個數字，之後在遍歷時第一個股價就會成為最低價）。
第2步： 遍歷每一天的股價。如果今天的價格比之前遇到的最低價格還低，就把最低價格更新為今天的價格 ; 如果今天賣股票賺的錢比之前都賺的多，那就更新最大利潤。
第3步： return最大利潤。
程式碼：

def max_profit(prices)
  min_price = Float::INFINITY #假設一個超巨數字
  max_profit = 0

  prices.each do |price| #訪問每天的股價
    min_price = [min_price, price].min #更新變量，並保持在最低價
    max_profit = [max_profit, price - min_price].max #更新目前為止的最大利潤
  end

  max_profit
end

🔎 總結

時間複雜度

貪婪演算法： 時間複雜度為O(n)
➡️ 其實應該還要有動態規劃跟暴拆法的，不過兩者效率都不高，這題如果用暴拆法的話根本就是略過階乘這個好方法不用直接用加法加到死的概念，而動態規劃的結構也很複雜。因為沒有必要學更複雜的東西，所以就只寫了貪婪法附上注解啦(´∇｀*)ノ～

那麽，以上就是今天的內容嚕！明天是最後一題easy了ㄛ！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃哇沙比口味的花生豆。
明天要說：Ruby精選刷題！練等要先從easy開始V(>∀･)⌒☆